package Hot_100;/*
    24. 两两交换链表中的节点
        给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。
        你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
    提示:
        链表中节点的数目在范围 [0, 100] 内
        0 <= Hot_100.Node.val <= 100
* */

import org.junit.Test;

/*
    思路: 要考虑到链表结点个数为奇偶数的情况

* */
public class T24_swapPairs {
    @Test
    public void test() {
        ListNode l1 = new ListNode(1);
        ListNode l2 = new ListNode(2);
        ListNode l3 = new ListNode(4);
        ListNode l4 = new ListNode(5);
        ListNode l5 = new ListNode(8);
        l1.next = l2;
        l2.next = l3;
        l3.next = l4;
        l4.next = l5;
        l5.next = null;
        ListNode head = swapPairs(l1);
        while (head != null) {
            System.out.print(head.val+" ");
            head = head.next;
        }
    }


//    迭代
    public ListNode swapPairs(ListNode head) {
//        if (head == null||head.next == null){ //空链表or只有一个结点
//            return head;
//        }

        ListNode p = new ListNode();  //p作为头结点方便链表的操作
        p.next=head;
        ListNode p1, p2, tmp;
        p1 = p2 = tmp = p;
        while (tmp != null && tmp.next != null && tmp.next.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
            tmp.next = p2;
            p1.next = p2.next;
            p2.next = p1;
            p2 = p1;
            tmp = p1;
        }
        return p.next;
    }


//  递归求解
    public ListNode swapPairs_2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode next = head.next;
        head.next = swapPairs_2(next.next);     //head.next 指向下一个子链表的head结点
        next.next=head;
        return next;
    }
}